<?php

define('OPT_SIZE_UNKNOWN',999999999);
define('OPT_VAR_BINDS_WILL_BIND',2);
define('OPT_VAR_BINDS_MAY_BIND',1);
define('OPT_VAR_BINDS_NONE',0);
define('OPT_VAR_NEEDS_GROUND',2);
define('OPT_VAR_NEEDS_CHECK',1);
define('OPT_VAR_NEEDS_NONE',0);

define('RDFS_TYPE','http://www.w3.org/1999/02/22-rdf-syntax-ns#type');

class OptItem {
	var $rawItem;
	var $analysis;
	var $freeVars;
	var $freeVarInfo;  // varname => FREE (for bound() function) | GROUND (for use by filters) | 
	                   //            MAY_BIND (for optional blocks) | WILL_BIND
	function __construct($optimiser,$rawItem) {
		$this->rawItem = $rawItem;
		$this->analysis = $optimiser->analyse($rawItem);
		$this->freeVarInfo = $optimiser->getFreeVars($rawItem);
		$this->freeVars = array_keys($this->freeVarInfo);
	}
	
	function __toString() {
		return (string)$rawItem;
	}
	
	static function getRawItemFromOptItem($item) {
		return $item->rawItem;
	}
	
	static function combineBindLevels($bind1,$bind2) {
		$bind = $bind1;
		$bind['needs'] = max($bind1['needs'],$bind2['needs']);
		$bind['binds'] = max($bind1['binds'],$bind2['binds']);
		return $bind;
		/*
		foreach ( array( 'WILL_BIND', 'MAY_BIND', 'BOUND' ) as $bind_level ) {
			if ( $bind1 == $bind_level || $bind2 == $bind_level ) {
				return $bind_level;
			}
		}
		return 'FREE';
		*/
	}
	
	static function makeBindsWillBind() {
		return array( 'binds'=>OPT_VAR_BINDS_WILL_BIND );
	}
	
	static function makeNeedsGround() {
		return array( 'needs'=>OPT_VAR_NEEDS_GROUND );
	}
	
	static function softenCallBoundFreeVar() {
		if ( $bindlevel['needs'] == OPT_VAR_NEEDS_GROUND ) {
			$bindlevel['needs'] = OPT_VAR_NEEDS_CHECK;
		}
		return $bindlevel;
	}

	static function softenOptionalFreeVar($bindlevel) {
		if ( $bindlevel['binds'] == OPT_VAR_BINDS_WILL_BIND ) {
			$bindlevel['binds'] = OPT_VAR_BINDS_MAY_BIND;
		}
		return $bindlevel;
		/*
		if ( $bindlevel == 'WILL_BIND' ) {
			return 'MAY_BIND';
		} else {
			return $bindlevel;
		}
		*/
	}
	
	static function itemBoundVarStats($item,$bindings,$potentialBindings=false) {
		//echo "itemBoundVarStats(".print_r($item,true)." )\n";
		$counts = array( 'ALL' => 0, 'CHECK' => 0, 'GROUND' => 0, 'MAY_BIND' => 0, 'WILL_BIND' => 0 );
		//echo "itemBoundVarStats:freevarInfo=".print_r($item->freeVarInfo,true)."\n";
		//echo "itemBoundVarStats:analysis=".print_r($item->analysis,true)."\n";
		$analysis = $item->analysis;
		foreach( $item->freeVarInfo as $var => $info ) {
			$is_bound = false;
			$maybe_bound = false;
			$may_bind_later = false;
			$will_bind_later = false;
			if ( array_key_exists($var,$bindings)) {
				$binding = $bindings[$var];
				// *********** initially ignore all but full bindings - ordering triples
				if ( $binding['kind'] == 'IS_BOUND' ) {
					$is_bound = true;
				} else if ( $binding['kind'] == 'MAYBE_BOUND' ) {
					$maybe_bound = true;
				}
			}
			if ( $potentialBindings && array_key_exists($var,$potentialBindings)) {
				$binding = $potentialBindings[$var];
				// *********** initially ignore all but full bindings - ordering triples
				if ( $binding['binds'] == OPT_VAR_BINDS_WILL_BIND ) {
					$will_bind_later = true;
				} else if ( $binding['binds'] == OPT_VAR_BINDS_MAY_BIND ) {
					$may_bind_later = true;
				}
			}
			$poss_bind_later = $will_bind_later || $may_bind_later;
			if ( $is_bound ) {
				//echo "itemBoundVarStats: adding binding for $var \n";
				if ( $analysis['vars'] && array_key_exists($var,$analysis['vars']) ) {
					$analysis = $analysis['vars'][$var];
				}
			} else { // var is not bound
				//echo "itemBoundVarStats: adding counts for $var \n";
				$counts['ALL']++;
				if ( $info['needs'] == OPT_VAR_NEEDS_CHECK && $poss_bind_later ) $counts['CHECK']++;
				if ( $info['needs'] == OPT_VAR_NEEDS_GROUND && $poss_bind_later ) $counts['GROUND']++;
				if ( $info['binds'] == OPT_VAR_BINDS_MAY_BIND  ) $counts['MAY_BIND']++;
				if ( $info['binds'] == OPT_VAR_BINDS_WILL_BIND  ) $counts['WILL_BIND']++;
			}
		}
		$counts['tripleCount'] = $analysis['tripleCount'];
		//echo "itemBoundVarStats(".$item->rawItem['p']."::".implode(",",array_keys($bindings))."):counts=".print_r($counts,true)."\n";
		return $counts;
	}
	
	static function addVarsToBinding($item,$bindings) {
		//echo "addVarsToBinding \n";
		foreach( $item->freeVarInfo as $var => $info ) {
			//echo " processing $var => ".print_r($info,1)." \n";
			switch ( $info['binds'] ) {
				case OPT_VAR_BINDS_WILL_BIND:
					$bindings[$var] = array( 'kind' => 'IS_BOUND');
					break;
				case OPT_VAR_BINDS_MAY_BIND:
					if ( array_key_exists($var,$bindings) ) {
						if ( $bindings[$var]['kind'] != 'BOUND' ) {
							$bindings[$var]['kind'] = 'MAYBE_BOUND';
						}
					} else {
						$bindings[$var] = array( 'kind' => 'MAYBE_BOUND');
					}
					break;
				default:
					break; // free and must be bound variables do not create new bindings
			}
		}
		//echo " returns bindings: ".implode(",",array_keys($bindings))." \n";
		return $bindings;
	}
	
	
	/*
	* @returns < 0 if item1 is less good than item2; > 0 if item1  is better than item2, and 0 if they are equal.
	*/
	static function compareItemByVarBinding($item1,$item2,$bindings) {
		$stats1 = self::itemBoundVarStats($item1,$bindings);
		$stats2 = self::itemBoundVarStats($item2,$bindings);
		if ( $stats1['ALL'] < $stats2['ALL'] ) return 1;  // better to have fewer free variables
		else if ( $stats1['ALL'] > $stats2['ALL'] ) return -1;
		
		if ( $stats1['GROUND'] < $stats2['GROUND'] ) return 1;  // better to have fewer variables that must be bound
		else if ( $stats1['GROUND'] > $stats2['GROUND'] ) return -1;
		
		if ( $stats1['CHECK'] < $stats2['CHECK'] ) return 1;  // better to need to check fewer variables are bound
		else if ( $stats1['CHECK'] > $stats2['CHECK'] ) return -1;
		
		if ( $stats1['WILL_BIND'] < $stats2['WILL_BIND'] ) return -1;  // better to bind more variables
		if ( $stats1['WILL_BIND'] > $stats2['WILL_BIND'] ) return 1;
		
		if ( $stats1['MAY_BIND'] < $stats2['MAY_BIND'] ) return -1;  // better to at least maybe bind more variables
		else if ( $stats1['MAY_BIND'] > $stats2['MAY_BIND'] ) return 1;
		
		if ( $stats1['tripleCount'] < $stats2['tripleCount'] ) return 1;  // better to reduce number of triples
		else if ( $stats1['tripleCount'] > $stats2['tripleCount'] ) return -1;
		
		if ( $item1->rawItem['p'] == RDFS_TYPE ) {
			if ( $item2->rawItem['p'] == RDFS_TYPE ) {
				// do nout the same
			} else {
				echo "{$item1->rawItem['p']} is worse than {$item2->rawItem['p']} \n";
				return -1;   // assume rdfs-type is weak binding
			}
		} else 	 {
			if ( $item2->rawItem['p'] == RDFS_TYPE ) {
				echo "{$item1->rawItem['p']} is better than {$item2->rawItem['p']} \n";
				return 1;   // assume rdfs-type is weak binding
			} else {
				// do nout the same
			}
		}
		return 0;
		//return $stats2['initialOrder'] - $stats1['initialOrder'];  // use given order as tie breaker
	}
	
	static function sortItemByVarBinding($itemlist,$bindings=array()) {
		$len = count($itemlist);
		if ( $len <= 1 ) {
			return $itemlist;
		}
		//for ( $index=0; $index < $len; $index++ ) {
		//	$itemlist[$index]['initialOrder'] = $index;
		//}
		$sorted = array();
		//echo "initial bindings: ".implode(",",array_keys($bindings))." \n";
		while ( $len > 0 ) {
			//echo "sortItemByVarBinding: len=$len \n";
			
			$best = 0;
			for ( $index=1; $index < $len; $index++ ) {
				//echo "sortItemByVarBinding: index=$index best=$best \n";
				//echo "compare " . print_r($itemlist[$index],true). " with " . print_r($itemlist[$best],true) . "\n";
				if ( self::compareItemByVarBinding($itemlist[$index],$itemlist[$best],$bindings) > 0 ) {
					$best = $index;
				}
			}
			//echo "sortItemByVarBinding: best=$best \n";
			$bestItem = $itemlist[$best];
			$sorted[] = $bestItem;
			array_splice( $itemlist, $best, 1 );  // removes the item at $best
			$len--;
			$bindings = self::addVarsToBinding($bestItem,$bindings);
			//echo " best was ".$bestItem->rawItem['p']." bindings: ".implode(",",array_keys($bindings))." \n";
		}
		//echo "======  sortItemByVarBinding\n";  print_r($sorted); echo "\n=========\n\n";
		return $sorted;
	}
	
}

class Optimiser {
	var $schemaStats;
	var $store;
	var $query;
	var $optimised;
	
	var $top_level_triples;
	
	var $status;  
	var $reason = array();  
	
	function __construct($schemaStats,$store=false) {
		$this->schemaStats = $schemaStats;
		$this->store = $store;
	}
	
	function setStore($store) {
		$this->store = $store;
	}

	
   /*
	* @param $query array structure as returned from ARC2 parser getQueryInfos 
	*/

	function optimise($query) {
		$this->query = $query;
		$this->status = 'WORKING';
		$this->_optimise();
		if ( $this->status == 'FAIL' ) {
			$this->optimised = $this->query;
		} else {
			$this->status = 'OK';
		}
		return $this->optimised;
	}
	
	function fail($reason) {
		$this->status = 'FAIL';
		$this->reason[] = $reason;
		return false;
	}

	function _optimise() {
		$this->_gather_top_level_items() && 
		$this->_sort_triples() && 
		$this->_rebuild_query() && 
		true;
	}
	
	function makeOptItemFromRawItem($item) {
		return new OptItem($this,$item);
	}
	
	function _sort_triples() {
		$triples = $this->top_level_items['triples'];
		$itemTriples = array_map(array($this,'makeOptItemFromRawItem'),$this->top_level_items['triples']);
		$itemOptions = array_map(array($this,'makeOptItemFromRawItem'),$this->top_level_items['options']);
		$itemFilters = array_map(array($this,'makeOptItemFromRawItem'),$this->top_level_items['filters']);
		
		$orderedTriples = OptItem::sortItemByVarBinding($itemTriples);
		$this->orderedOptItems = array_merge($orderedTriples,$itemOptions,$itemFilters);
		//echo "======  _sort_triples\n";  print_r($orderedTriples); echo "\n=========\n\n";
		//echo "======  _sort_triples: orderedOptItems=\n";  print_r($this->orderedOptItems); echo "\n=========\n\n";
		return true;
	}
	
	function _rebuild_query() {
		$orderedRawItems = array_map(array('OptItem','getRawItemFromOptItem'),$this->orderedOptItems);
		$tripleGatheredItems = $this->_gather_triples_from_items($orderedRawItems);
		
		$this->optimised = $this->query;
		$this->optimised['query']['pattern'] = array( 'type'=>'group', 'patterns'=>$tripleGatheredItems );
		return true;
	}
	
	function _gather_triples_from_items($items) {
		//echo "======  _gather_triples_from_items\n";  print_r($items); echo "\n=========\n\n";
		$patterns = array();
		$triples = array();
		foreach( $items as $item ) {
			if ( $item['type'] == 'triple' ) {
				$triples[] = $item;
			} else {
				if ( $triples ) {
					$patterns[] = array( 'type'=>'triples', 'patterns'=>$triples );
					$triples = array();
				}
				$patterns[] = $item;
			}
		}
		if ( $triples ) {
			$patterns[] = array( 'type'=>'triples', 'patterns'=>$triples );
			$triples = array();
		}
		//echo "======  _gather_triples_from_items\n";  print_r($patterns); echo "\n=========\n\n";
		return $patterns;
	}
	
	function _gather_top_level_items() {
		if ( $this->query['query']['pattern']['type'] != 'group') {
			return $this->fail('query pattern is not group');
		}
		$top_level = $this->_flatten_pattern($this->query['query']['pattern']);
		$this->top_level_items = $top_level;
		//echo "======  _gather_top_level_items\n";  print_r($top_level); echo "\n=========\n\n";
		return true;
	}
	
	function _merge_flattened_parts($parts_arr,$init=false) {
		if ( $init ) {
			$allparts = $init;
		} else {
			$allparts = array('triples'=>array(),'options'=>array(),'filters'=>array());			
		}
		foreach( $parts_arr as $parts ) {
			$allparts['triples'] = array_merge($allparts['triples'],$parts['triples']);
			$allparts['options'] = array_merge($allparts['options'],$parts['options']);
			$allparts['filters'] = array_merge($allparts['filters'],$parts['filters']);
		}
		return $allparts;
	}

	function _flatten_pattern($pattern) {
		$parts = array('triples'=>array(),'options'=>array(),'filters'=>array());
		switch ( $pattern['type'] ) {
			case 'group':
					$group_parts = array_map(array('Optimiser','_flatten_pattern'), $pattern['patterns']);
					$parts = $this->_merge_flattened_parts($group_parts,$parts);
					break;
			case 'triples':
					$parts['triples'] = array_merge( $parts['triples'],  $pattern['patterns'] );
					break;
			case 'optional':
					$parts['options'][] = $pattern;
					break;
			case 'filter':
					$parts['filters'][] = $pattern;
					break;
			default:
					$this->fail( 'unrecognised pattern type '.$pattern['type'] );
					break;
		}
		return $parts;
	}
	
	
	static function mergeAnalysis($analysis_array) {
		return array( 'type' => 'merged' );
	}
		
	function analyse($pattern) {
		$analysis = array( 'type' => $pattern['type'], 'tripleCount'=>OPT_SIZE_UNKNOWN );
		switch ( $pattern['type'] ) {
			case 'group':
			case 'triples':
			case 'optional':
					break;
			case 'triple':
					//echo "analyse_triple: \n Pattern: " . print_r($pattern,true) ."\n";
					$analysis = $this->analyse_triple($pattern);
					//echo	" Result: " . print_r($analysis,true) ."\n";
					break;
			case 'filter':
					break;
			default:
					break;
		}
		return $analysis;
	}
	
	function analyse_triple($pattern) {
		$analysis = array( 'type' => 'triple', 'tripleCount'=>OPT_SIZE_UNKNOWN );
		
		if ( $pattern['p_type'] != 'uri'  ) {
			return $analysis;  // give up!
		}
		
		$predicate = $pattern['p'];
		$p_stats = $this->schemaStats->getPredicateStatistics($predicate);
		if ( !$p_stats || $p_stats['tripleCount']==0 ) {
			echo "no information for $predicate \n";
			return $analysis;
		}
		$tripleCount = $p_stats['tripleCount'];
		$distinctObjectCount = $p_stats['distinctObjectCount'];
		$distinctSubjectCount = $p_stats['distinctSubjectCount'];
		$triples_per_subj = ((double)$tripleCount) / ((double)$distinctSubjectCount);
		$triples_per_obj = ((double)$tripleCount) / ((double)$distinctObjectCount);
		
		$allBoundAnalysis = array( 'type'=>'triple', 'tripleCount'=>1 );
		$subjBoundAnalysis = array( 'type'=>'triple', 'tripleCount'=>$triples_per_subj,
										'vars'=>array( $pattern['o']=>$allBoundAnalysis ) );
		$objBoundAnalysis = array( 'type'=>'triple', 'tripleCount'=>$triples_per_obj,
										'vars'=>array( $pattern['s']=>$allBoundAnalysis ) );
		$neitherBoundAnalysis = array( 'type'=>'triple', 'tripleCount'=>$tripleCount,
										'vars'=>array( $pattern['s']=>$subjBoundAnalysis,
														  $pattern['o']=>$objBoundAnalysis ) );
		
		if ( $pattern['s_type'] == 'var' ) {
			if ( $pattern['o_type'] == 'var' ) {
				return $neitherBoundAnalysis;
			} else { // only object is bound
				return $objBoundAnalysis;
			}
		} else {
			if ( $pattern['o_type'] == 'var' ) {
				return $subjBoundAnalysis;
			} else {
				return $allBoundAnalysis;
			}
		}
		
		
	}
/*
	static function _analyse_expressions($expressionList) {
		$fv_list = array_map( array('Optimiser','_analyse_expression'), $expressionList );
		return self::mergeAnalysis($fv_list);
	}

	static function _analyse_expression($expression) {
		//echo ("_fv_expression: ".print_r($expression['type'],true)."\n");
		switch ( $expression['type'] ) {
			case 'expression':
				$mergedAnalysis = self::_analyse_expressions($expression['patterns']);
				$freevars = $mergedAnalysis['freevars'];
				break;
			case 'built_in_call':
				$mergedAnalysis = self::_analyse_expressions($expression['args']);
				$freevars = $mergedAnalysis['freevars'];
				if (  $expression['call'] == 'bound' ) {
					$freevars = array_map( array('OptItem','softenCallBoundFreeVar'), $freevars );
				}
				break;
			case 'var':
				$freevars = array( $expression['val']=>OptItem::makeNeedsGround() );
				break;
			case 'uri': case 'literal':
				$freevars = array();
				break;
			default:
				echo ("expression is not an expression but a ".$expression['type']."\n");
				$freevars = array();
				break;
		}
		return array( 'type'=>$expression['type'], 'freevars'=>$freevars );
	}
*/
	static function getFreeVars($pattern) {
		switch ( $pattern['type'] ) {
			case 'group':
			case 'triples':
			case 'optional':
					$freevars = array_map(array('Optimiser','getFreeVars'),$pattern['patterns']);
					if ( $pattern['type'] ==  'option');
					$freevars = array_map( array('OptItem','softenOptionalFreeVar'), $freevars );
					break;
			case 'triple':
					$freevars = array();
					if ( $pattern['s_type'] == 'var' ) {
						$freevars[$pattern['s']] = OptItem::makeBindsWillBind();
					}
					if ( $pattern['p_type'] == 'var' ) {
						$freevars[$pattern['p']] = OptItem::makeBindsWillBind();
					}
					if ( $pattern['o_type'] == 'var' ) {
						$freevars[$pattern['o']] = OptItem::makeBindsWillBind();
					}
					if ( $pattern['p_type'] == 'literal'  ) {
						
					}
					break;
			case 'filter':
					echo ("getFreeVars: filter ".print_r($pattern,true)."\n");
					$freevars = self::_fv_expression($pattern['constraint']);
					break;
			default:
					echo('unrecognised pattern type '+$pattern['type']."\n");
					$freevars = array();
					break;
		}
		return $freevars;
	}

	static function mergeFreevars($freevar_array) {
		$all_freevars = array();
		foreach( $freevar_array as $freevars) {
			foreach( $freevars as $var => $bind ) {
				if ( ! array_key_exists( $var, $all_freevars ) ) {
					$all_freevars[$var] = $bind;
				} else {
					$all_freevars[$var] = OptItem::combineBindLevels($all_freevars[$var],$bind);
				}
			}
		}
		return $all_freevars;
	}
		
	static function _fv_expressions($expressionList) {
		$fv_list = array_map( array('Optimiser','_fv_expression'), $expressionList );
		return self::mergeFreevars($fv_list);
	}

	static function _fv_expression($expression) {
		//echo ("_fv_expression: ".print_r($expression['type'],true)."\n");
		switch ( $expression['type'] ) {
			case 'expression':
				$freevars = self::_fv_expressions($expression['patterns']);
				break;
			case 'built_in_call':
				$freevars = self::_fv_expressions($expression['args']);
				if (  $expression['call'] == 'bound' ) {
					$freevars = array_map( array('OptItem','softenCallBoundFreeVar'), $freevars );
				}
				break;
			case 'var':
				$freevars = array( $expression['val']=>OptItem::makeNeedsGround() );
				break;
			case 'uri': case 'literal':
				$freevars = array();
				break;
			default:
				echo ("expression is not an expression but a ".$expression['type']."\n");
				$freevars = array();
				break;
		}
		return $freevars;
	}
}



?>